class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution1:
    """
    解法：中序遍历输出一个列表，检查列表是否是递增排列
    """

    def __init__(self):
        self.result = []

    def isValidBST(self, root: TreeNode) -> bool:
        result = self.inorder(root)
        for i in range(len(result) - 1):
            if result[i] >= result[i + 1]:
                return False
        return True

    def inorder(self, root):
        """
        中序遍历函数
        :param root:
        :return:
        """
        if root:
            self.inorder(root.left)
            self.result.append(root.val)
            self.inorder(root.right)
        return self.result


class Solution2:
    """
    中序遍历，记录上一个节点，比较当前节点与上一个节点的值的大小
    """

    def __init__(self):
        self.pre = None

    def isValidBST(self, root: TreeNode) -> bool:
        if not root:
            return False
        return self.inorder(root)

    def inorder(self, root: TreeNode) -> bool:
        """
        中序遍历函数
        :param root:
        :return:
        """
        left = right = True
        if root.left:
            left = self.inorder(root.left)
        if self.pre and self.pre.val >= root.val:
            return False
        self.pre = root
        if root.right:
            right = self.inorder(root.right)
        return left and right
